1. Field of the Invention
This invention relates to the field of programmable logic devices and, more particularly, to the use of simulated annealing to optimize such devices.
2. Description of the Related Art
Simulated annealing is an optimization technique frequently used with respect to the physical design of programmable logic devices (PLD's). As simulated annealing can be used to solve combinatorial optimization problems, the technique is commonly used to perform tasks such as partitioning, floorplanning, and placement for field programmable gate arrays (FPGA's).
The technique seeks to explore multi-dimensional solution spaces to find an optimal solution through random generation of new combinatorial configurations. To generate a new configuration, an old or previous configuration is shuffled at random. For example, the configuration can be shuffled by displacing an object to a random location, exchanging locations of two or more objects, or performing other adjustments to the design that can affect a cost function. The cost function serves as a means of evaluating the quality of the proposed solution or move in view of predetermined design constraints.
Each configuration, such as a proposed placement solution, can be accepted or rejected based upon an evaluation of the cost function. If a decrease in the cost function occurs, the new configuration is accepted. Otherwise, the new configuration can be accepted with a probability that depends upon “temperature”.
As simulated annealing was inspired through an analogy with the cooling of metals, the iterative process is regulated by a cooling schedule that dictates temperature. The cooling schedule specifies an initial temperature, a final temperature, and a function for changing the temperature which restricts the allowable moves in the annealing process as the temperature decreases. Accordingly, the exploration of different placement solutions is stressed at high temperatures, while the convergence to a particular solution is stressed at lower temperatures.
Though simulated annealing can provide high quality solutions for PLD designs, the process requires significant computational resources. To overcome this need, various techniques for reducing the amount of time and computing resources required have been proposed. These approaches have addressed controlled move generation, i.e. the selection of an object to move and a target location, parallel implementation of simulated annealing, and cooling schedule improvements.
Conventional simulated annealing techniques operate such that each movable object has an equal likelihood of being selected for displacement for controlled move generation. This probability can be expressed as: Pr(i)=1/N, where N is the total number of identical objects and
            ∑              i        =        1            N        ⁢                  ⁢          Pr      ⁡              (        i        )              =  1.The target location also is selected among all available locations with equal probability, at least within a range limited area.
One proposed solution has been to evaluate the historical contribution of moving a particular object in light of changes to the cost function. For example, a histogram of cost function contribution for each object can be stored and evaluated. Objects having a history indicative of improvements to the cost function as a result of displacement can be favored over other objects during selection for controlled move generation. By increasing the probability that objects having a favorable histogram are selected, the likelihood of converging upon a solution more rapidly is increased.
Still, this solution does not take into account device specific design considerations such as congestion, timing delay, and the like. Accordingly, it would be beneficial to provide a technique for simulated annealing that encourages selection of objects and/or target locations for controlled move generation with respect to design considerations. It would further be beneficial to provide a technique for selecting objects and/or target locations that is independent of the cost function.